package com.hfb.mashibing.alip8.juc;

/**
 * ConcurrentLinkedQueue 的源码分析
 *
 * 概念
 * 并编程中，一般需要用到安全的队列，如果要自己实现安全队列，可以使用2种方式：
 * 方式1：加锁，这种实现方式就是我们常说的阻塞队列。
 * 方式2：使用循环CAS算法实现，这种方式实现队列称之为非阻塞队列。
 * 先对而已，加锁队列的实现较为简单，这里就略过，我们来重点来解读一下非阻塞队列。
 * 从点到面， 下面我们来看下非阻塞队列经典实现类：ConcurrentLinkedQueue （JDK1.8版）
 *
 * ConcurrentLinkedQueue 是一个基于链接节点的无界线程安全的队列，按照先进先出原则对元素进行排序。新元素从队列尾部插入，
 *  而获取队列元素，则需要从队列头部获取。
 *
 *  ConcurrentLinkedQueue使用特点
 * ConcurrentLinkedQueue使用约定：
 * 1:不允许null入列
 * 2:在入队的最后一个元素的next为null
 * 3:队列中所有未删除的节点的item都不能为null且都能从head节点遍历到
 * 4:删除节点是将item设置为null, 队列迭代时跳过item为null节点
 * 5:head节点跟tail不一定指向头节点或尾节点，可能存在滞后性
 *
 * 之所以有这奇葩约定，全因ConcurrentLinkedQueue是并发非阻塞队列决定的。
 *
 * 入列、出列 利用CAS实现无锁并发线程安全，但是遍历不安全。
 *
 * HOPS的设计：
 * 通过上面对offer和poll方法的分析，我们发现tail和head是延迟更新的，两者更新触发时机为：
 *
 * tail更新触发时机：
 *  当tail指向的节点的下一个节点不为null的时候，会执行定位队列真正的队尾节点的操作，
 *      找到队尾节点后完成插入之后才会通过casTail进行tail更新；
 *  当tail指向的节点的下一个节点为null的时候，只插入节点不更新tail。
 *
 * head更新触发时机：
 *  当head指向的节点的item域为null的时候，会执行定位队列真正的队头节点的操作，
 *      找到队头节点后完成删除之后才会通过updateHead进行head更新；
 *  当head指向的节点的item域不为null的时候，只删除节点不更新head。
 *
 * 总结：
 * ConcurrentLinkedQueue贴点：
 * 1> 入列出列线程安全，遍历不安全
 * 2> 不允许添加null元素
 * 3> 底层使用列表与cas算法包装入列出列安全
 *
 * 使用场景：https://cloud.tencent.com/developer/article/1340018
 *      由于ConcurrentLinkedQueue是无界的，所以使用的时候要特别注意内存溢出问题。
 *      akka的actor模型，默认的mailbox是用这个来实现的。
 */
public class MyConcurrentLinkedQueue {

}
